/*
 * @lc app=leetcode.cn id=763 lang=cpp
 *
 * [763] 划分字母区间
 */

// @lc code=start
class Solution
{
public:
    vector<int> partitionLabels(string s)
    {
        //分割字母区间 首先需要找到每个字母最后出现的位置
        //然后遍历字符串 如果当前位置与字母最后出现位置相等 说明可以分割
        int map[27] = {};
        for (int i = 0; i < s.size(); i++)
        {
            map[s[i] - 'a'] = i;
        }
        int start = 0;
        int end = 0;
        vector<int> res;
        for (int i = 0; i < s.size(); i++)
        {
            end = max(end, map[s[i] - 'a']);
            if (end == i)
            {
                res.push_back(i - start + 1);
                start = i + 1;
            }
        }
        return res;
    }
};
// @lc code=end
